class Solution:
    def climbStairs(self, n: int) -> int:

        s = [0] * n
        s[0],s[1] = 1,2
        for i in range(2,n):
            s[i] = s[i-1]+s[i-2]

        return s[n-1]


if __name__ == '__main__':
    n = 3
    solution = Solution()
    val = solution.climbStairs(n)
    print(val)
